package sword_offer;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @ClassName _59_2_MaxQueue
 * @Description: 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
 *
 * 若队列为空，pop_front 和 max_value 需要返回 -1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/11 12:37
 */
public class _59_2_MaxQueue {

    class MaxQueue {
        private Deque<Integer> dataQueue;

        private Deque<Integer> maxValueDeque;

        public MaxQueue() {
            dataQueue = new LinkedList<>();
            maxValueDeque = new LinkedList<>();
        }

        public int max_value() {
            return maxValueDeque.isEmpty()? -1 : maxValueDeque.peekFirst();
        }

        public void push_back(int value) {
            // data_queue
            dataQueue.addLast(value);

            // handle max_value_queue
            while (!maxValueDeque.isEmpty() && maxValueDeque.peekLast() < value)
                maxValueDeque.removeLast();
            maxValueDeque.addLast(value);
        }

        public int pop_front() {
            // data_queue pop
            if (dataQueue.isEmpty())// 这里判断是否为空，否则下面会出现NoSuchElement异常
                return -1;
            int popValue = dataQueue.removeFirst();

            // handle max_value_queue
            if (popValue == maxValueDeque.peekFirst())
                maxValueDeque.poll();

            return popValue;
        }
    }
}
